package hot100;

import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.List;

public class CanFinish {
    List<List<Integer>> edge = new ArrayList<>();//边集合

    int[] state;

    boolean valid = true;//是否有效，无环

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //定义3个状态，0：未搜索；1：搜索中（还在这条深搜链路）；2：（搜索完）当前节点的深搜链路搜索完
        //先初始化每个边集合
        for (int i = 0; i < numCourses; i++) {
            edge.add(new ArrayList<>());
        }
        //状态列表
        state = new int[numCourses];//值为0，1，2
        //遍历数组，添加边
        for (int i = 0; i < prerequisites.length; i++) {
            edge.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        //深搜，找出是否有环
        for (int i = 0; i < numCourses && valid; i++) {
            if (state[i] == 0) {
                //未搜索，去进行深搜
                dfs(i);
            }
        }

        return valid;
    }

    private void dfs(int i) {
        state[i] = 1;//改为搜索中
        //遍历边
        List<Integer> ends = edge.get(i);
        ends.stream().forEach(end -> {
            if (state[end] == 0) {
                dfs(end);
            } else if (state[end] == 1) {
                //在搜索中的节点再一次被搜索到，形成环，设为false
                valid = false;
                return;
            }
        });

        //当前链路遍历完成，状态修改为搜索完
        state[i] = 2;
    }



}
